As data storage densities and data transmission rates increase, the ability of hardware devices to correctly recognize binary data diminishes. Such binary data, which comprises a string of bits, i.e., zeros and ones, must be correctly recognized so as to facilitate the proper interpretation of the information represented thereby. That is, each individual zero and one needs to be interpreted reliably, so as to facilitate the accurate reconstruction of the stored and/or transmitted data represented thereby.
Such increased storage densities and transmission rates place a heavy burden upon the hardware utilized to recognize the state of individual bits. In contemporary storage devices, high storage densities dictate that the individual data bits be stored very close to one another. Further, in some data storage systems, the difference between the manner in which a one and a zero is stored in the media is not great enough to make the reading thereof as reliable as desired.
High data transmission rates imply either that the time allocated for each bit is substantially reduced, or that a modulation scheme is utilized wherein small differences in amplitude, frequency, and/or phase indicate a distinct sequence of bits, e.g., such as in multi-bit modulation. In either instance, the ability of hardware devices to accurately and reliably interpret such transmitted data is substantially reduced.
Although modern data storage systems are generally capable of limiting read errors to approximately one bit in ten billion, the extremely high volume of data processing typically being performed in contemporary data processing systems makes even such a seemingly low error rate unacceptable. In many systems, such an error rate would result in at least one error per day.
It must be appreciated that the incorrect reading of even a single bit of data may have highly undesirable effects. For example, the incorrect reading of a single bit of a computer program may cause the program to lock up or otherwise function incorrectly. Also, the incorrect reading of a single bit of numeric data may cause a number to be misread, which may have serious consequences when dealing with financial data, for example.
As those skilled on the art will appreciate, increasing data storage density and/or increasing data transmission speed inherently increases the bit error rate, i.e., the percentage of error bits contained in a message. It is desirable to be able to identify and correct data errors which occur during data storage and/or transmission operations. By being able to identify and correct such data errors, data may be stored more densely and/or transmitted more rapidly.
Further, the ability to correct data errors facilitates the use of mechanical devices, e.g., record/read heads, which are manufactured according to reduced tolerances and which are therefore less expensive. That is, hardware may be utilized which is more prone to introducing data errors, but which costs less.
Moreover, the ability to correct errors facilitates storage and transmission of data in low signal to noise environments. Thus, since data errors can be corrected, more noise can be tolerated within a storage medium (or rather the data signal can be recorded at a lower level as compared to the noise level, thus facilitating higher storage densities). Similarly, more noise can also be tolerated in data transmission, thereby facilitating increased data transmission speed.
The ability to store and transmit data in low signal to noise environments provides substantial benefit in satellite/spacecraft communications, compact disc (CD) recording, high definition television (HDTV), digital versatile disc (DVD) recording, network communications, and the like. In satellite/spacecraft communications, a weak signal (low signal to noise ratio) inherently results from the use of low power transmitters necessitated by weight constraints. In compact disc (CD) and digital disc (DVD) recording, being able to record in low signal to noise environments facilitates increased storage densities. In high definition television (HDTV) and network communications, being able to operate in low signal to noise environments facilitates communication at increased data transmission rates.
Error detection and correction methodologies for determining the existence of errors in stored and/or transmitted data and for correcting those errors are well known. Among the simplest of these methodologies is the use of data redundancy, wherein the data is repeated several times when it is stored or transmitted. When the data is read, a particular data error is unlikely to affect more than one occurrence of the data, such that a majority vote results in the correct data being recognized.
For example, a data byte may be stored three times. A data error is likely to affect only one of these three stored data bytes. Thus, the two correctly stored data bytes constitute a majority with respect to the incorrectly stored data byte, thereby identifying the data error and assuring correct interpretation of the stored data. However, as those skilled in the art will appreciate, such a majority vote method is extremely inefficient, since the data must be stored or transmitted several, e.g., 3, times. It is preferable to utilize an error detection and correction methodology which requires as few added bits to the message data as possible. This tends to minimize storage requirements and maximize transmission speed.
In an effort to overcome the deficiencies associated with the inefficient methodology of the majority vote system, various means for providing data correction which add only a few extra bits to the data have evolved. For example, the well known use of parity bits provides a much mnore efficient scheme for indicating the presence of a data error, although the use of simple parity alone does not facilitate the correction of such errors. When only parity error detection is used, then incorrectly transmitted data must be re-transmitted. Thus, although corrupt data is readily identifiable, corrupt data which was only present in a storage medium, and thus is not available for re-transmission, may not be recoverable.
Since it does not facilitate error correction without retransmission, parity is not a forward error correction methodology. In forward error correction methodologies, sufficient information is added to the stored or transmitted data to facilitate the reliable correction of data errors without requiring such retransmission, as long as a mathematically determined error rate is not exceeded.
It is desirable to provide a methodology for correcting burst errors. Burst errors involve the corruption of a plurality of consecutive bits. Burst errors are common in data storage and data transmission.
Burst errors typically occur during data storage due to faulty media. For example, a scratch or other imperfection upon a magnetic or optical storage medium may result in the loss or corruption of many consecutive bits stored upon the medium.
Burst errors typically occur during data transmission due to noise or static within the transmission frequency band. Signal fading and cross-talk may also cause burst errors during data transmission.
The well known Reed-Solomon encoding methodology provides an efficient means of error detection which also facilitates forward error correction, wherein a comparatively large number of data errors in stored and/or transmitted data can be corrected.
Reed-Solomon encoding is particularly well suited for correcting burst errors, wherein a plurality of consecutive bits become corrupted. For example, the implementation of Reed-Solomon encoding currently used to store information upon compact discs (CDs) is capable of correcting error bursts containing as many as four thousand consecutive bits.
Reed-Solomon encoding is based upon the arithmetic of finite fields. A basic definition of Reed-Solomon encoding states that encoding is performed by mapping from a vector space of M over a finite field K into a vector space of higher dimension over the same field. Essentially, this means that with a given character set, redundant characters are utilized to represent the original data in a manner which facilitates reconstruction of the original data when a number of the characters have become corrupted.
This may be better understood by visualizing Reed-Solomon code as specifying a polynomial which defines a smooth curve containing a large number of points. The polynomial and its associated curve represent the message. That is, points upon the curve are analogous to data points. A corrupted bit is analogous to a point that is not on the curve, and therefore is easily recognized as bad. It can thus be appreciated that a large number of such bad points may be present in such a curve without preventing accurate reconstruction of the proper curve (that is, the desired message). Of course, for this to be true, the curve must be defined by a larger number of points than are mathematically required to define the curve, so as to provide the necessary redundancy.
If N is the number of elements in the character set of the Reed-Solomon code, then the Reed-Solomon encode is capable of correcting a maximum of t errors, as long as the message length is less than N-2t.
Although the use of Reed-Solomon encoding provides substantial benefits by enhancing the reliability with which data may be stored or transmitted, the use of Reed-Solomon encoding according to contemporary practice possesses inherent deficiencies. These deficiencies are associated with the decoding of Reed-Solomon encoded data. It should be noted that in many applications, the encoding process is less critical than the decoding process. For example, since CDs are encoded only once, during the mastering process, and subsequently decoded many times by users, the encoding process can use slower, more complex and expensive technology. However, decoding must be performed rapidly to facilitate real-time use of the data, e.g., music, programs, etc., and must use devices which are cost competitive in the consumer electronics market. Thus, it is desirable to provide a VLSI device for performing Reed-Solomon decoding, since such VLSI devices tend to be comparatively fast and inexpensive.
Decoding Reed-Solomon encoded data involves the calculation of an error locator polynomial and an error evaluator polynomial. One of two methods is typically utilized to decode Reed-Solomon encoded data. The Berlekamp-Massey algorithm is the best known technique for finding the error locator. The Berlekamp-Massey algorithm is capable of being implemented in a VLSI chip. However, the Berlekamp-Massey algorithm utilizes an inversion process which undesirably increases the complexity of such a VLSI design and which is computationally intensive, thereby undesirably decreasing the speed of decoding process.
Also well known is the use of Euclid's algorithm for the decoding of Reed-Solomon encoded data. However, Euclid's algorithm utilizes a polynomial division methodology which is computationally intensive and which is difficult to implement in VLSI.
In view of the foregoing, it is desirable to provide a method for decoding Reed-Solomon encoded data which is easily and economically implemented as a VLSI chip and which is computationally efficient so as to substantially enhance decoding speed.